﻿int[] list = [1, 2,4,3, 5, 8, 9, 10, 11, 2, 3];
InsertionSort(list);
foreach (int i in list)
{
	Console.Write(i + " ");
}

/* 插入排序 */
void InsertionSort(int[] nums) {
	// 外循环：已排序区间为 [0, i-1]
	for (int i = 1; i < nums.Length; i++) {
		int bas = nums[i], j = i - 1;
		// 内循环：将 base 插入到已排序区间 [0, i-1] 中的正确位置
		while (j >= 0 && nums[j] > bas) {
			nums[j + 1] = nums[j]; // 将 nums[j] 向右移动一位
			j--;
		}
		nums[j + 1] = bas;         // 将 base 赋值到正确位置
	}
}
